import java.util.*;

class Solution {
    private List<String> list = new ArrayList<>();

    public String[] permutation(String s) {
        char[] arr = s.toCharArray();
        dfs(arr, 0);
        return list.toArray(new String[0]);
    }

    private void dfs(char[] arr, int k) {
        if (k == arr.length - 1) {
            list.add(new String(arr));
            return;
        }
        Set<Character> set = new HashSet<>();
        for (int i = k; i < arr.length; i++) {
            if (set.contains(arr[i])) {
                continue;
            }
            set.add(arr[i]);
            swap(arr, k, i);
            dfs(arr, k + 1);
            swap(arr, k, i);
        }
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        String[] res = s.permutation("abb");
        System.out.println(Arrays.toString(res));
    }
}